package pro1_10.pro4;

import java.util.ArrayList;

public class tree {
    private node root;

    public tree(){
        root = new node();
    }

    public tree(int value){
        root = new node(value);
    }

    public void insert(int value){
        if(root == null){
            root = new node(value);
        }else{
            insertHelp(value,root);
        }
    }

    private void insertHelp(int value, node currNode){
        if(value < currNode.getData()){
            if(currNode.getLeft() == null){
                currNode.setLeft(new node(value));
            }else {
                //左
                insertHelp(value, currNode.getLeft());
            }
        }
        if(value > currNode.getData()){
            if(currNode.getRight() == null){
                currNode.setRight(new node(value));
            }else {
                insertHelp(value,currNode.getRight());
            }
        }
        if(value == currNode.getData()){
            ;
        }
    }

    public void print(){
        if(root == null){
            ;
        } else{
            printHelp(root);
        }
    }

    private void printHelp(node currNode){
        if(currNode != null){
            printHelp(currNode.getLeft());
            System.out.print(currNode.getData() + " ");
            printHelp(currNode.getRight());
        }
    }

    public void getSum(int value){
        if(root == null){
            return ;
        }
        if(root.getData() == value){
            System.out.println(root.getData());
        }else {
            getSumHelp(value, root, 0, new ArrayList<Integer>());
        }
    }

    private void getSumHelp(int value, node currNode, int sum, ArrayList<Integer> result){
        if(currNode != null){
            result.add(currNode.getData());
            sum = sum + currNode.getData();
            if(value == sum && (currNode.getRight() == null && currNode.getLeft() == null)){
                for(Integer i : result){
                    System.out.print(" " + i);
                }
            }
            getSumHelp(value , currNode.getLeft(), sum, result);
            getSumHelp(value , currNode.getRight(), sum, result);
            result.remove(result.size()-1);
        }
    }

}
